1. Field of the Invention
The invention relates to a method for adaptive arbitration of requests for memory access in a multi-stage pipeline engine, more particularly to a method for adaptive arbitration of requests for accessing a memory unit in a multi-stage pipeline engine that can reduce the occurrence of idling or stalling in the multi-stage pipeline engine.
2. Description of the Related Art
A pipeline architecture is commonly found in integrated circuit designs. When processing 3D graphic digital data, generation of 3D graphics includes the steps of geometry and image rendering. Since movement and operation of a large amount of pixel data are needed during processing, a 3D pipeline engine is utilized for increasing throughput of 3D commands.
Referring to FIG. 1, a conventional n-stage pipeline engine 10 includes an arbiter 110, a memory unit 12 for storing different types of data, such as red, green and blue pixel values, alphavalue, Z value, texture data, etc., and a plurality of request queues 131, 131xe2x80x2, 131xe2x80x3 and data buffers 130, 130xe2x80x2, 130xe2x80x3 for increasing efficiency of the n-stage pipeline engine 10. The different types of data are accessed in different stages of the n-stage pipeline engine 10. For each request of data access, one of the request queues and a corresponding one of the data buffers are used. The request queue and the corresponding data buffer can be located in different stages, such as the request queue A 131 and the data buffer A 130, and the request queue B 131xe2x80x2 and the data buffer B 130xe2x80x2, or in the same stage, such as the request queue C 131xe2x80x3 and the data buffer C 130xe2x80x3, of the n-stage pipeline engine 10.
In the example of FIG. 1, the second and (nxe2x88x923)th stages in the n-stage pipeline engine 10 have the request queue A 131 and the request queue B 131xe2x80x2, respectively, for storing a request therein. When the arbiter 110 serves the request, data associated with the request are read from the memory unit 12. The fourth and (nxe2x88x922)th stages in the n-stage pipeline engine 10 have the data buffer A 130 and the data buffer B 130xe2x80x2, respectively, for storing the data that is associated with the request. The nth stage in the n-stage pipeline engine 10 has the request queue C 131xe2x80x3 and the data buffer C 130xe2x80x3. When the memory unit 12 is busy or in a memory bound state, the data buffer C 130xe2x80x3 stores data to be written to the memory unit 12 so as to minimize stalling while waiting for data access. Furthermore, when the operational speed of the second stage in the n-stage pipeline engine 10 is faster than that of the third stage in the n-stage pipeline engine 10, the output data from the second stage cannot be received instantly by the third stage, thereby resulting in stalling at the second stage. Therefore, a data buffer, such as a pixel FIFO 15, which is located between the second and third stages, is used to store pixel data from the second stage to minimize stalling at the second stage.
The arbiter 110 assigns a fixed priority to the request queues 131, 131xe2x80x2, 131xe2x80x3 in a known manner. The order of the request queues 131, 131xe2x80x2, 131xe2x80x3 is determined according to locations of the corresponding data buffers in the n-stage pipeline engine 10. The arbiter 110 assigns the high-priority request queue to that whose associated data buffer is located farthest from an upstream end of the n-stage pipeline engine 10. The following are some of the drawbacks of the fixed priority scheme of the arbiter 110:
1. Since the arbiter 110 does not consider the nature of memory requests and the state of the memory unit 12, reduced utilization of the memory unit 12 can result.
2. Since the arbiter 110 assigns a fixed priority to minimize stalling of the n-stage pipeline engine, bubbling (many stages in the n-stage pipeline engine 10 are idle) may occur when a data buffer located in an upstream side of the n-stage pipeline engine 10 is empty and another data buffer located in a downstream side of the n-stage-pipeline engine 10 is not empty. Referring to FIG. 1, when the data buffer B 130xe2x80x2 located in the (nxe2x88x922)th stage is empty and the data buffer C 130xe2x80x3 located in the nth stage is not empty, the arbiter 110 processes data stored in the data buffer C 130xe2x80x3 until the data buffer C 130xe2x80x3 is empty, thereby resulting in idling of the (nxe2x88x922)th stage. When the data buffer C 130xe2x80x3 is empty, due to the idling of the (nxe2x88x922)th stage that results in the data buffer B 130xe2x80x2 still being empty, the (nxe2x88x921)th, nth stages will be idle.
Therefore, an object of the present invention is to provide a method for adaptive arbitration of requests for memory access in a multi-stage pipeline engine that can reduce the occurrence of idling or stalling in the pipeline engine.
According to the present invention, a method is adapted for adaptive arbitration of requests for accessing a memory unit in a multi-stage pipeline engine that includes a plurality of request queues corresponding to the stages of the pipeline engine. The method comprises the steps of:
(a) assigning each of the request queues to one of a high-priority group and a low-priority group in accordance with an operating state of the memory unit; and
(b) processing the request queues in the high-priority group prior to the request queues in the low-priority group.